package com.sheng.leetcode.year2025.month09.day21;

import org.junit.Test;

import java.util.*;

/**
 * @author by ls
 * @date 2025/9/28
 * <p>
 * 1912. 设计电影租借系统<p>
 * <p>
 * 你有一个电影租借公司和 n 个电影商店。你想要实现一个电影租借系统，它支持查询、预订和返还电影的操作。同时系统还能生成一份当前被借出电影的报告。<p>
 * 所有电影用二维整数数组 entries 表示，<p>
 * 其中 entries[i] = [shopi, moviei, pricei] 表示商店 shopi 有一份电影 moviei 的拷贝，<p>
 * 租借价格为 pricei 。每个商店有 至多一份 编号为 moviei 的电影拷贝。<p>
 * 系统需要支持以下操作：<p>
 * Search：找到拥有指定电影且 未借出 的商店中 最便宜的 5 个 。<p>
 * 商店需要按照 价格 升序排序，如果价格相同，则 shopi 较小 的商店排在前面。<p>
 * 如果查询结果少于 5 个商店，则将它们全部返回。如果查询结果没有任何商店，则返回空列表。<p>
 * Rent：从指定商店借出指定电影，题目保证指定电影在指定商店 未借出 。<p>
 * Drop：在指定商店返还 之前已借出 的指定电影。<p>
 * Report：返回 最便宜的 5 部已借出电影 （可能有重复的电影 ID），将结果用二维列表 res 返回，<p>
 * 其中 res[j] = [shopj, moviej] 表示第 j 便宜的已借出电影是从商店 shopj 借出的电影 moviej 。<p>
 * res 中的电影需要按 价格 升序排序；如果价格相同，则 shopj 较小 的排在前面；如果仍然相同，则 moviej 较小 的排在前面。<p>
 * 如果当前借出的电影小于 5 部，则将它们全部返回。如果当前没有借出电影，则返回一个空的列表。<p>
 * 请你实现 MovieRentingSystem 类：<p>
 * MovieRentingSystem(int n, int[][] entries) 将 MovieRentingSystem 对象用 n 个商店和 entries 表示的电影列表初始化。<p>
 * List<Integer> search(int movie) 如上所述，返回 未借出 指定 movie 的商店列表。<p>
 * void rent(int shop, int movie) 从指定商店 shop 借出指定电影 movie 。<p>
 * void drop(int shop, int movie) 在指定商店 shop 返还之前借出的电影 movie 。<p>
 * List<List<Integer>> report() 如上所述，返回最便宜的 已借出 电影列表。<p>
 * 注意：测试数据保证 rent 操作中指定商店拥有 未借出 的指定电影，且 drop 操作指定的商店 之前已借出 指定电影。<p>
 * <p>
 * 示例 1：<p>
 * 输入：<p>
 * ["MovieRentingSystem", "search", "rent", "rent", "report", "drop", "search"]<p>
 * [[3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]], [1], [0, 1], [1, 2], [], [1, 2], [2]]<p>
 * 输出：<p>
 * [null, [1, 0, 2], null, null, [[0, 1], [1, 2]], null, [0, 1]]<p>
 * 解释：<p>
 * MovieRentingSystem movieRentingSystem = new MovieRentingSystem(3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]);<p>
 * movieRentingSystem.search(1);  // 返回 [1, 0, 2] ，商店 1，0 和 2 有未借出的 ID 为 1 的电影。商店 1 最便宜，商店 0 和 2 价格相同，所以按商店编号排序。<p>
 * movieRentingSystem.rent(0, 1); // 从商店 0 借出电影 1 。现在商店 0 未借出电影编号为 [2,3] 。<p>
 * movieRentingSystem.rent(1, 2); // 从商店 1 借出电影 2 。现在商店 1 未借出的电影编号为 [1] 。<p>
 * movieRentingSystem.report();   // 返回 [[0, 1], [1, 2]] 。商店 0 借出的电影 1 最便宜，然后是商店 1 借出的电影 2 。<p>
 * movieRentingSystem.drop(1, 2); // 在商店 1 返还电影 2 。现在商店 1 未借出的电影编号为 [1,2] 。<p>
 * movieRentingSystem.search(2);  // 返回 [0, 1] 。商店 0 和 1 有未借出的 ID 为 2 的电影。商店 0 最便宜，然后是商店 1 。<p>
 * <p>
 * 提示：<p>
 * 1 <= n <= 3 * 10^5<p>
 * 1 <= entries.length <= 10^5<p>
 * 0 <= shopi < n<p>
 * 1 <= moviei, pricei <= 10^4<p>
 * 每个商店 至多 有一份电影 moviei 的拷贝。<p>
 * search，rent，drop 和 report 的调用 总共 不超过 10^5 次。<p>
 */
public class LeetCode1912 {

    @Test
    public void test() {
        // entries[i] = [shopi, moviei, pricei] 表示商店 shopi 有一份电影 moviei 的拷贝，
        // 租借价格为 pricei 。每个商店有 至多一份 编号为 moviei 的电影拷贝。
        int[][] entries = {{0, 1, 5}, {0, 2, 6}, {0, 3, 7}, {1, 1, 4}, {1, 2, 7}, {2, 1, 5}};
        MovieRentingSystem movieRentingSystem = new MovieRentingSystem(3, entries);
        // 返回 [1, 0, 2] ，商店 1，0 和 2 有未借出的 ID 为 1 的电影。商店 1 最便宜，商店 0 和 2 价格相同，所以按商店编号排序。
        System.out.println(movieRentingSystem.search(1));
        // 从商店 0 借出电影 1 。现在商店 0 未借出电影编号为 [2,3] 。
        movieRentingSystem.rent(0, 1);
        // 从商店 1 借出电影 2 。现在商店 1 未借出的电影编号为 [1] 。
        movieRentingSystem.rent(1, 2);
        // 返回 [[0, 1], [1, 2]] 。商店 0 借出的电影 1 最便宜，然后是商店 1 借出的电影 2 。
        System.out.println(movieRentingSystem.report());
        // 在商店 1 返还电影 2 。现在商店 1 未借出的电影编号为 [1,2] 。
        movieRentingSystem.drop(1, 2);
        // 返回 [0, 1] 。商店 0 和 1 有未借出的 ID 为 2 的电影。商店 0 最便宜，然后是商店 1 。
        System.out.println(movieRentingSystem.search(2));
    }
}

class MovieRentingSystem {
    private Map<Integer, Map<Integer, int[]>> shopMovies;
    private Map<Integer, TreeSet<int[]>> availableMovies;
    private TreeSet<int[]> rentedMovies;

    /**
     * 将 MovieRentingSystem 对象用 n 个商店和 entries 表示的电影列表初始化。
     *
     * @param n       n 个商店
     * @param entries 电影列表
     */
    public MovieRentingSystem(int n, int[][] entries) {
        shopMovies = new HashMap<>();
        availableMovies = new HashMap<>();
        rentedMovies = new TreeSet<>((a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0];
            if (a[1] != b[1]) return a[1] - b[1];
            return a[2] - b[2];
        });

        for (int[] entry : entries) {
            int shop = entry[0], movie = entry[1], price = entry[2];
            shopMovies.putIfAbsent(shop, new HashMap<>());
            shopMovies.get(shop).put(movie, entry);
            availableMovies.putIfAbsent(movie, new TreeSet<>((a, b) -> {
                if (a[0] != b[0]) return a[0] - b[0];
                return a[1] - b[1];
            }));
            availableMovies.get(movie).add(new int[]{price, shop, movie});
        }
    }

    /**
     * 返回 未借出 指定 movie 的商店列表。
     *
     * @param movie 指定 movie 的商店列表
     * @return
     */
    public List<Integer> search(int movie) {
        List<Integer> result = new ArrayList<>();
        if (!availableMovies.containsKey(movie)) return result;
        int count = 0;
        for (int[] entry : availableMovies.get(movie)) {
            if (count >= 5) break;
            result.add(entry[1]);
            count++;
        }
        return result;
    }

    /**
     * 从指定商店 shop 借出指定电影 movie 。
     *
     * @param shop  指定商店 shop
     * @param movie 指定电影 movie
     */
    public void rent(int shop, int movie) {
        int[] entry = shopMovies.get(shop).get(movie);
        int price = entry[2];
        availableMovies.get(movie).remove(new int[]{price, shop, movie});
        rentedMovies.add(new int[]{price, shop, movie});
    }

    /**
     * 在指定商店 shop 返还之前借出的电影 movie 。
     *
     * @param shop  指定商店 shop
     * @param movie 返还之前借出的电影 movie
     */
    public void drop(int shop, int movie) {
        int[] entry = shopMovies.get(shop).get(movie);
        int price = entry[2];
        rentedMovies.remove(new int[]{price, shop, movie});
        availableMovies.get(movie).add(new int[]{price, shop, movie});
    }

    /**
     * 返回最便宜的 已借出 电影列表。
     * 注意：测试数据保证 rent 操作中指定商店拥有 未借出 的指定电影，且 drop 操作指定的商店 之前已借出 指定电影。
     *
     * @return
     */
    public List<List<Integer>> report() {
        List<List<Integer>> result = new ArrayList<>();
        int count = 0;
        for (int[] entry : rentedMovies) {
            if (count >= 5) break;
            result.add(Arrays.asList(entry[1], entry[2]));
            count++;
        }
        return result;
    }
}

/**
 * Your MovieRentingSystem object will be instantiated and called as such:
 * MovieRentingSystem obj = new MovieRentingSystem(n, entries);
 * List<Integer> param_1 = obj.search(movie);
 * obj.rent(shop,movie);
 * obj.drop(shop,movie);
 * List<List<Integer>> param_4 = obj.report();
 */
